1. Field of the Invention
The invention relates to a method and an apparatus for controlling accumulation error produced by digit truncation due to digit truncation in a non-integer computation, and more particular to a method and an apparatus for controlling an accumulated error after fast rotation.
2. Description of the Related Art
The amount of information in digital images, especially in high definition television (HDTV) images and high resolution medical X-ray images, is enormous. With the aid of image coding techniques, the total amount of image data can be reduced to an acceptable amount. Transforming coding is one of the most efficient methods of data compression for correlated signals.
It has been proved theoretically that Givens rotation based on rotation arithmetic to achieve various orthogonal transforms has the optimal data stability or robustness. However, since the word length of transform coefficient is limited for hardware implementation, so that a template error is produced for rotation. This error is static and is independent of input signal. On the other hand, the intermediary computation results under transform processing are stored. But the word length of the storage unit is limited. As a consequence, digits have to be truncated or omitted. The truncated digits are result in calculation error. The calculation error is dynamic and is dependent of input data. In a rotation network, the error is transferable. The calculation error is accumulated in each step of hardware implementation. The path to produce a maximum calculating error is called an error accumulating critical path. Evaluation of error range according to the error accumulating critical path, the reserved internal bus bits for accumulated errors are obtained.
The calculation error in a fast rotator is introduced by shift-addition calculation of fast rotation. The implemented hardware for this shift-addition calculation comprises a shifter, for example, a barrel shifter, and an adder/subtractor.
A conventional adder/subtractor is shown as FIG. 1. The conventional adder/subtractor comprises two terminals for data input of A and B. The input data B output from the shifter 104 is to go through an exclusive OR (XOR) 102 before being input into a full adder 101. An addition/subtraction selecting signal, as, is input into the same XOR 102 as the input data B. The terminal of the least significant bit (LSB) input C.sub.in is coupled to the addition/subtraction selecting signal terminal, so that as=C.sub.in. The resultant output is denoted as S.
The schematic drawing for the operation of the shifter 104 is shown as FIG. 2. Under the digit shift process, an input data B.sub.in is right shifted. The sign digits, that is, the most significant digit (MSB) are right shifted, so that an expansion of sign digits Exp is obtained. Since the input data B.sub.in has been right shifted, a number of digits T near the LSB are truncated. The right-shift is directed as the arrow Rs, and the output data B is as shown in the figure.
Under certain condition of fast rotation pipeline, the input data B is always small. By setting as=C.sub.in, S is always smaller than the correct value for addition operation (for an error less than 1LSB is set as 1). On the contrary, S is always larger for subtraction operation with as=C.sub.in. As shown in FIG. 3, since the addition/subtraction operation is performed in random, the error .epsilon..sub.i of each stage is evenly distributed within the interval [-1,1]. The expectation value of this distribution is 0, whereas the standard deviation is ##EQU1## For the error produced in a critical path of 512 pipelines which are needed to perform 32.times.32 block image transform, the expectation value is 0, and the standard deviation is ##EQU2## Setting 3.sigma. is the range of error, only 3% of the actual error is out of this range. The probability decreases abruptly with increasing the values which are out of this range. Therefore, a reserving bits for accumulated error is 6 (to allow 3.sigma..ltoreq.64).